1. Field of the Invention
Aspects of the present invention generally relate to signatures that are provably secure to the sending and receiving parties of an information exchange. More specifically, a challenge-response signature scheme possesses the property that both the verifier and the signer can compute the same or related signatures, the former by knowing the challenge and the latter by knowing the private signature key, thereby permitting, in exemplary embodiments, provably-secure variations of conventional key-exchange protocols, including a variation of the well-known MQV protocol.
2. Description of the Related Art
Diffie-Hellman (DH) key-exchange protocol 100 shown in FIG. 1, as originally proposed, is believed to be secure against an eavesdropping-only attacker. The quest for an “authenticated Diffie-Hellman” protocol that resists active, man-in-the-middle attacks has resulted in innumerable ad-hoc proposals, many of which have been broken or shown to suffer from drawbacks. With the development in the last years of rigorous security models for key exchange, those in the art are now in a much better position to judge the security of these protocols, as well as to develop designs that provably withstand realistic active attacks.
As expected, adding safeguards against active attacks results in added complexity, both in terms of additional communication and computation. The latter is particularly significant in protocols authenticated with public key techniques, which usually require additional costly group exponentiation. In addition to the need for sound security, the many practical applications to key exchange have driven designers to improve on the performance cost associated with authentication mechanisms, especially those based on a public key.
One line of investigation, initiated by Matsumoto, Takashima and Imai in 1986, is the search for a public-key (PK) authenticated DH protocol that would add minimal complexity to the protocol. Ideally, and up to the exchange of certified public keys, the protocol's communication is desired to look exactly as the basic DH exchange. In this technique, authentication of the protocol must be obtained via the key derivation procedure: rather than agreeing on the basic Diffie-Hellman key gxy, the parties would agree on a key that combines gx, gy with the public/private keys of the parties.
Due in part to the practical advantages that such a protocol would offer, and in part to the mathematical challenge behind such a design, many protocols have been developed under this approach, often referred to as “implicitly authenticated Diffie-Hellman protocols”. Not only can this approach generate protocols that are very efficient communication-wise, but the combination of authentication with the key derivation procedure can potentially result in significant computational savings. For these reasons, several of these “implicitly authenticated” protocols have been standardized by major national and international security standards.
Of these protocols, the MQV protocol appears to have been widely standardized. This protocol has been standardized by many organizations and has recently been announced by the U.S. National Security Agency (NSA) to be the key exchange mechanism underlying “the next generation cryptography to protect US government information”, which includes the protection of “classified or mission critical national security information.”
Further, MQV appears to have been designed to satisfy an array of security goals. A basic version of the MQV protocol is explained, for example, in U.S. Pat. No. 5,761,305 to Vanstone et al., the entire contents of which are herein incorporated by reference.
Yet, in spite of its attractiveness and success, MQV has so far eluded any formal analysis in a well-defined model of key exchange. The present invention was motivated by the desire to provide such an analysis. Upon conducting a study, the inventor observed that virtually none of the stated MQV goals can be shown to hold, as carried out in the computational key exchange model of Canetti and Krawczyk, and as described in the provisional Application identified above.
This result raised concerns to the present inventor about the security of this conventional protocol. Therefore, based on this analysis that the conventional MQV protocol was not provably secure, there exists a need for additional security to MQV, while preferably retaining its existing performance and versatility.